\[ \newcommand{\IR}{\mathbb{R}} \newcommand{\IRnn}{\IR_{\geq 0}} \newcommand{\IRp}{\IR_{\gt 0}} \newcommand{\coloneqq}{\mathbin{:=}} \newcommand{\eqqcolon}{\mathbin{=:}} \newcommand{\coloniff}{\mathbin{:\!\!\iff}} \newcommand{\dcup}{\mathbin{\dot\cup}} \newcommand{\sMid}{\,|\,} \newcommand{\SMid}{\middle|} \newcommand{\abs}[1]{\lvert#1\rvert} \newcommand{\Abs}[1]{\left\lvert#1\right\rvert} \newcommand{\norm}[1]{\lVert#1\rVert} \newcommand{\Norm}[1]{\left\lVert#1\right\rVert} \newcommand{\PSet}[1]{2^{#1}} \newcommand{\transp}{^\top} \newcommand{\eps}{\varepsilon} \]

Improving-Moves Algorithm (cf. Ex. 1/5)

Input: finite strategic game $G=(N,S,u)$, strategy profile $s \in S$
Output: A PNE $s^\ast \in S$ of $G$

While $s$ is not a PNE Do
mmchoose $i \in N$ and $s'_i \in S_i$ with $u_i(s'_i,s_{-i}) \gt u_i(s)$
mmset $s \leftarrow (s'_i,s_{-i})$
Return $s$

	$L$	$C$	$R$
$T$	$(4,2)$	$(2,3)$	$(3,1)$
$B$	$(2,6)$	$(5,4)$	$(4,6)$

For $G=(N,S,u)$:

deviation graph $\mathcal{G}(G) \coloneqq (S,E)$ with $e=(s,s') \in E \iff \exists i \in N, s' = (s'_i,s_{-i})$
improvement path $\gamma=(s^0,s^1,\dots)$: path in $\mathcal{G}(G)$ with $u_i(s^{k-1}) \lt u_i(s^k)$ for $i \in N$ with $s^k = (s^k_i,s^{k-1}_{-i})$ f.a. $k$
$G$ has finite improvement property (FIP) $\coloniff$ every improvement path in $\mathcal{G}(G)$ is finite

§3 Potential Games

For game $G=(N,S,u)$ and vector $b \in \IRp^N$, a function $P: S \to \IR$ is

exact potential	$\coloniff \forall s \in S, i \in N, s'_i \in S_i: u_i(s'_i,s_{-i}) - u_i(s) = \phantom{b_i\cdot\bigl(}P(s'_i,s_{-i}) - P(s)$
$b$-potential	$\coloniff \forall s \in S, i \in N, s'_i \in S_i: u_i(s'_i,s_{-i}) - u_i(s) = b_i\cdot\bigl(P(s'_i,s_{-i}) - P(s)\bigr)$
ordinal potential	$\coloniff \forall s \in S, i \in N, s'_i \in S_i: u_i(s'_i,s_{-i}) \gt u_i(s) \iff \phantom{\bigl(} P(s'_i,s_{-i}) \gt P(s)$
generalized ordinal potential	$\coloniff \forall s \in S, i \in N, s'_i \in S_i: u_i(s'_i,s_{-i}) \gt u_i(s) \implies \phantom{\bigl(} P(s'_i,s_{-i}) \gt P(s)$

$s \in S$ local maximum of $P$ $\coloniff \forall i \in N, s'_i \in S_i: P(s'_i,s_{-i}) \leq P(s)$

Thm. 3.5: Game $G$ with ordinal potential $P$. Then

$s \in S$ local maximum of $P \iff s$ PNE of $G$
$P$ attains its maximum $\implies$ $G$ has PNE

Thm. 3.6: For finite game $G$: $G$ has FIP $\iff$ $G$ has generalized ordinal potential

Cor. 3.7: Any finite, generalized ordinal game has a PNE.

Thm. 3.10: $G$ has exact potential iff $\exists G^C=(N,S,u^C), G^D=(N,S,u^D)$ s.th.:

$G^C$ coordination game, i.e., $\forall i,j \in N: u^C_i = u_j^C$
$G^D$ dummy game, i.e., $\forall i \in N, s_{-i} \in S_{-i}: u^D(.,s_{-i}) = \mathrm{const.}$
$G=G^C+G^D$, i.e., $\forall i \in N: u_i = u^C_i + u^D_i$

Cor. 3.11: Exact potentials are unique up to additive constant.

Thm. 3.12: For any game $G$ the following are equivalent:

$G$ is an exact potential game
$\forall \gamma$ 4-cycle in $\mathcal{G}(G)$: $\Delta^u(\gamma)=0$
$\forall \gamma,\gamma'$ paths in $\mathcal{G}(G)$ with common start and end: $\Delta^u(\gamma) = \Delta^u(\gamma')$

For $\gamma = (s^0,s^1,\dots,s^K)$ path in $\mathcal{G}(G)$: \[\Delta^u(\gamma) \coloneqq \sum\nolimits_{k=1}^K\bigl(u_{i_k}(s^k)-u_{i_k}(s^{k-1})\bigr),\] with $i_k \in N$ s.th. $s^k=(s^k_i,s^{k-1}_{-i})$, is net-improvement along $\gamma$.